package LeetCode_138;

import java.util.HashMap;
import java.util.Map;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/11/19 15:02
 */
public class Solution2 {
    public Node copyRandomList(Node head) {
        // 需要一种映射关系
        // 从老的结点到新结点的对应映射关系
        // 问： Node 是否需要重写 hashCode 和 equals 方法
        // 回答：可以不重写，即 Object 中默认的方法即可
        // 默认：hashCode() 每个对象返回一个唯一的值
        // 默认：equals() 比较 ==
        // 在我们当下的场景中没有问题
        Map<Node, Node> map = new HashMap<>();

        // 复制
        Node ans = new Node(-1);
        Node last = ans;
        Node cur = head;
        while (cur != null) {
            Node node = new Node(cur.val);
            node.random = cur.random;

            // cur 指向老结点
            // node 指向新结点

            // 保存这种映射关系
            map.put(cur, node);

            // 同时，将 node 尾插到结果链表中
            last.next = node;
            last = node;

            cur = cur.next;
        }

        // 修改新链表中的 random 关系
        Node newCur = ans.next;
        while (newCur != null) {
            if (newCur.random != null) {
                // newCur.random 指向的老链表的结点
                // 通过 map 这个映射关系，找到新链表中的对应结点
                Node newRandom = map.get(newCur.random);
                // 修改 node 的 random 关系到新链表的结点上
                newCur.random = newRandom;
            }

            newCur = newCur.next;
        }

        // 返回新链表
        return ans.next;
    }
}
